Quadratic kernelization for convex recoloring of trees

Title: Quadratic kernelization for convex recoloring of trees
Creator: Bodlaender, Hans L.; Fellows, Michael R.; Langston, Michael A.; Ragan, Mark A.; Rosamond, Frances A.; Weyer, Mark
Relation: Algorithmica Vol. 61, Issue 2, p. 362-388
Publisher Link: http://dx.doi.org/10.1007/s00453-010-9404-2
Publisher: Springer
Resource Type: journal article
Date: 2011
Description: The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078–1089, 2007; J. Comput. Syst. Sci. 74:850–869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/logk)^k n ⁴). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k²).
Subject: algorithms; combinatorial algorithms; fixed parameter tractability; kernelization; convex recoloring; trees; phylogeny
Identifier: http://hdl.handle.net/1959.13/936218
Identifier: uon:12243
Identifier: ISSN:0178-4617
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format